A search space is the set of all states or potential problem-solutions. Usually there is some form of structure, for example each potential solution may be defined by a set of parameters, or search tree. In game playing, the searh space is often a game tree with gemae states (for example board positions) linked by the palyers' moves. Often a reparametrisation that changes the representation of the states will also give an alterative structure to the search space making search easier. For optimisation problems each state also has soem sort of value given by a fitness function giving rise to a fitness landscape.
Used on Chap. 4: pages 80, 81; Chap. 7: page 143; Chap. 8: page 152; Chap. 11: pages 222, 234; Chap. 18: page 423